# 质数列表
def primesList(mx):
    primes = []
    isPrime = [True] * (mx + 1)
    isPrime[0], isPrime[1] = False, False
    for i in range(2, mx + 1):
        if isPrime[i]:
            primes.append(i)
        for p in primes:
            if i * p > mx:
                break
            isPrime[i * p] = False
            if i % p == 0:
                break
    return primes


## 最小最大因子
def mnmxFactors(mx):
    primes = []
    isPrime = [True] * (mx + 1)
    isPrime[0], isPrime[1] = False, False
    mxFactors = [1] * (mx + 1)
    mnFactors = [1] * (mx + 1)
    for i in range(2, mx + 1):
        if isPrime[i]:
            primes.append(i)
        for p in primes:
            if i * p > mx:
                break
            isPrime[i * p] = False
            mxFactors[i * p] = i
            mnFactors[i * p] = p
            if i % p == 0:
                break
    return mxFactors
